package com.leetcode.August;

/**
 * @Description: 在排序数组中查找元素的第一个和最后一个位置
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-04 09:28
 */
public class LC34在排序数组中查找元素的第一个和最后一个位置 {
    //    public int[] searchRange(int[] nums, int target) {
//        int start = lowerBound(nums, target); // 选择其中一种写法即可
//        if (start == nums.length || nums[start] != target) {
//            return new int[]{-1, -1}; // nums 中没有 target
//        }
//        // 如果 start 存在，那么 end 必定存在
//        int end = lowerBound(nums, target + 1) - 1;
//        return new int[]{start, end};
//    }
//
//    // lowerBound 返回最小的满足 nums[i] >= target 的 i
//    // 如果数组为空，或者所有数都 < target，则返回 nums.length
//    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
//
//    // 闭区间写法
//    private int lowerBound(int[] nums, int target) {
//        int left = 0, right = nums.length - 1; // 闭区间 [left, right]
//        while (left <= right) { // 区间不为空
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target) {
//                left = mid + 1; // 范围缩小到 [mid+1, right]
//            } else {
//                right = mid - 1; // 范围缩小到 [left, mid-1]
//            }
//        }
//        return left;
//    }
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target)return new int[]{-1,-1};
        return new int[]{start,lowerBound(nums,target+1)-1};
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

